package com.example.ten_sort_text.sort;

/**
 * 直接插入排序： 扑克牌
 * 1.从第一个元素开始，该元素可以认为已经被排序；
 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 * 5.将新元素插入到该位置后；
 * 6.重复步骤2~5。
 *
 */
public class ChaRuSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void sort(int[] arr){
        int lastIndext; // 排好序的数组中最后一个元素的下标
        int current;// 当前取出的需要排序的对比值
        for(int i = 0 ; i<arr.length; i++){
          lastIndext = i - 1;
          current = arr[i];
          while (lastIndext >= 0 && arr[lastIndext] > current){
              // 如果最后一个元素比当前对比值要大
              arr[lastIndext + 1] = arr[lastIndext]; // 将最后一个元素移动到下一位置
              lastIndext--; // 继续往前比较
            }
          arr[lastIndext +1] = current;
          // 循环结束，说明已经找到插入位置
        }
    }
}
